`
https://leetcode.cn/problems/course-schedule/
`

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  // 将依赖关系转换为图结构
  const buildGraph = () => {
    const graph = new Array(numCourses).fill(null).map(() => [])
    for (const edge of prerequisites) {
      const from = edge[1], to = edge[0]
      graph[from].push(to)
    }
    return graph
  }
  const graph = buildGraph()

  // 记录是否存在环
  let hasCycle = false

  // 记录在路径上的结点
  const onPath = new Array(numCourses).fill(false)
  // 记录已经遍历过的结点
  const visited = new Array(numCourses).fill(false)

  // 遍历
  const traverse = (cls) => {
    // 已经有环，不需要遍历了
    if (hasCycle) {
      return
    }

    // 遍历到在路径上的结点，说明有环
    if (onPath[cls]) {
      hasCycle = true
      return
    }

    // 遍历到已经被遍历过的结点，不用在遍历一次
    if (visited[cls]) {
      return
    }

    visited[cls] = true
    onPath[cls] = true

    for (const c of graph[cls]) {
      traverse(c)
    }

    onPath[cls] = false
  }

  for (let i = 0; i < numCourses; i++) {
    traverse(i)
  }

  return !hasCycle
};